#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution1 {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size() - 1;
        sort(citations.begin(), citations.end());

        int h = 0;
        while (n >= 0 && h < citations[n])
        {
            h++;
            n--;
        }

        return h;
    }
};


//int main()
//{
//    vector<int> nums({ 3,0,6,1,5 });
//    cout << Solution().hIndex(nums) << endl;
//
//	return 0;
//}

////////////////////////////////////
class Solution5 {
    vector<vector<int>> arr;
    vector<int> path;
public:
    int subsetXORSum(vector<int>& nums) {
        _subsetXORSum(nums, 0);

        int ans = 0, n = arr.size();
        for (int i = 0; i < n; i++)
        {
            int m = arr[i].size(), tmp = 0;
            for (int j = 0; j < m; j++)
            {
                tmp ^= arr[i][j];
            }

            ans += tmp;
        }
        return ans;
    }

    void _subsetXORSum(vector<int>& nums, int pos)
    {
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            arr.push_back(path);
            _subsetXORSum(nums, i + 1);
            path.pop_back();
        }
    }
};

//int main()
//{
//    vector<int> nums({ 1,3 });
//    Solution().subsetXORSum(nums);
//
//    return 0;
//}

///////////////////////
#include <string>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution6 {
public:
    string tree2str(TreeNode* root) {
        string str;
        _tree2str(root, str);

        return str;
    }

    void _tree2str(TreeNode* root, string& str)
    {
        if (root == nullptr)
        {
            return;
        }

        string tmp = to_string(root->val);
        str += tmp;
        if (root->left != nullptr || root->right != nullptr)
        {
            str.push_back('(');
            _tree2str(root->left, str);
            str.push_back(')');
        }

        if (root->right != nullptr)
        {
            str.push_back('(');
            _tree2str(root->right, str);
            str.push_back(')');
        }
    }
};


////////////////////////////
#include <stack>
#include <queue>
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;

        q.push(root);
        int n = 0;
        while (!q.empty())
        {
            int count = q.size();

            vector<int> tmp;
            while (count--)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }

            n++;
            ans.push_back(tmp);
        }

        return ans;
    }
};

//int main()
//{
//    //TreeNode* node1 = new TreeNode(3);
//    //TreeNode* node2 = new TreeNode(9);
//    //TreeNode* node3 = new TreeNode(20);
//    //TreeNode* node4 = new TreeNode(15);
//    //TreeNode* node5 = new TreeNode(7);
//    //node1->left = node2;
//    //node1->right = node3;
//    //node3->left = node4;
//    //node3->right = node5;
//
//    TreeNode* node1 = new TreeNode(1);
//
//
//    Solution().levelOrder(node1);
//    return 0;
//}


////////////////////////////////////////

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        stack<TreeNode*> st;
        stack<int> nums;
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;

        q.push(root);
        while (!q.empty())
        {
            int count = q.size();
            nums.push(count);

            while (count--)
            {
                TreeNode* front = q.front();
                q.pop();
                st.push(front);

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
        }

        while (!st.empty())
        {
            int count = nums.top();
            nums.pop();

            vector<int> tmp(count);
            while (count)
            {
                TreeNode* top = st.top();
                st.pop();

                tmp[--count] = top->val;
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};